The invention pertains to digital data processing and, more particularly, to image and signal processing and, still more particularly, by way of non-limiting example, to image processing operations that are based on convolution. The invention has application, by way of non-limiting example, in medical imaging, microscopy, and geo-sciences, to name but a few fields.
Convolution is an important image and signal processing operation. It is used, for example, in image reconstruction, image enhancement, and feature detection, among other critical operations. A formal statement of the challenge faced by designers of image and signal processing that perform convolution is as follows.
Given a digital image of size Nx×NyI(x,y), x=0, . . . , Nx−1, y=0, . . . , Ny−1, and a discrete filter kernel K(x,y), x=0, . . . , NxK−1, y=0, . . . , NyK−1 of size NxK×NyK, convolve or filter the image with that discrete filter kernel in accord with the formula:
                              o          ⁢                                          ⁢                      (                          x              ,              y                        )                          =                              ∑                          i              =              0                                                      N                x                K                            -              1                                ⁢                                          ⁢                                    ∑                              j                =                0                                                              N                  y                  K                                -                1                                      ⁢                                                  ⁢                          K              ⁢                                                          ⁢                              (                                  i                  ,                  j                                )                            ⁢                                                          ⁢              I              ⁢                                                          ⁢                              (                                                      x                    +                    i                    -                                          ⌊                                                                                                    N                            x                            K                                                    -                          1                                                2                                            ⌋                                                        ,                                      y                    +                    j                    -                                          ⌊                                                                                                    N                            y                            K                                                    -                          1                                                2                                            ⌋                                                                      )                                                                        (        1        )            
This formula evaluates the digital image outside its domain to compute output values near the boundaries. Depending on the application, different approaches for the boundary treatment may be chosen including defining pixels outside the domain to be a constant value, mirroring of the image, wrapping around or constant continuation.
For sake of simplicity, the challenge or problem statement, above, is expressed with respect to 2D images, as is (again, for sake of simplicity) much of the discussion in the sections below. However, as will be appreciated from the text below, both the challenge and the inventive solutions provided hereby can be applied to 1D as well as 3D or higher dimensions.
In view of the foregoing, an object of the invention is to provide improved methods and apparatus for digital data processing and particularly, for example, for image and signal processing.
A further object of the invention is to provide such methods and apparatus as provide improved performance of image and signal and signal processing operations based on convolution. A related object of the invention is to provide such methods and apparatus as provide for convolution or filtering of digital image data with discrete kernels.
Yet further objects of the invention are to provide such methods and apparatus as can be implemented at lower cost and, yet, as provide optimal performance.
A related object of the invention is to provide such methods and apparatus as can be implemented using standard, off-the-shelf components.